#pragma once

namespace Melting
{
namespace Parallel
{
	//--------------------------------------------------------------------------------------------------------------------
	template< class T, UINT32 TAG_INVALID_DATA >
    class LockFreeQueue
    { 
    public :
		//--------------------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------------------
        LockFreeQueue( UINT32 _iCapacity )
        :   miReadIndex			( 0 )
		,	miWriteIndex		( 0 ) 
		,	miCapacity          ( _iCapacity ) 
		{ 
			STATIC_ASSERT( sizeof(T) == 4, LockFreeQueue_works_only_with_32bits );

			MB_ASSERT( 0 != _iCapacity , "LockFreeQueue must have a non NULL capacity!\n" );
			MB_ASSERT( IsPowerOfTwo( _iCapacity ), "LockFreeQueue must have a capacity that is a power of 2!\n  Use the function GetNextPowerOfTwo(...) to find one\n" );

			maSlots = new Node[ _iCapacity ];

			for( UINT32 i = 0; i < _iCapacity; i++ )
			{
				maSlots[ i ].mKey	= i;
				maSlots[ i ].mData	= TAG_INVALID_DATA;
			}
        }

		//--------------------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------------------
		~LockFreeQueue( void )
        { 
            delete [] maSlots;
        }

		//--------------------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------------------
		FORCEINLINE bool Enqueue( const T& _rData )
		{
			//------------------------
			// precondition
			MB_ASSERT( TAG_INVALID_DATA != _rData, "Trying to Enqueue a TAG_INVALID_DATA ! That's forbidden.\n" );
			//------------------------ 
 			
			Node newNode;
 			newNode.mData	= _rData;

			Node currentNode;
 			currentNode.mData	= TAG_INVALID_DATA;
 
			while( ( miWriteIndex - miReadIndex ) < miCapacity )
			{
				const UINT32 iWrite = miWriteIndex; 
				
				//Parallel::MemoryBarrier(); // useless on MSVC 2005 and above, since volatile are treated as 'auto mem barriered'

				const UINT32 iSlot	= iWrite % miCapacity;
 
				currentNode.mKey	= iWrite;
				newNode.mKey		= iWrite;

 				if( currentNode.mValue == AtomicCompareAndSwap64bits( & maSlots[ iSlot ].mValue, newNode.mValue, currentNode.mValue ) )
				{ 
					AtomicIncrement( (volatile INT32*) & miWriteIndex );  
	
					//Parallel::MemoryBarrier(); 
					//------------------------
					// postcondition
					MB_ASSERT( TAG_INVALID_DATA == currentNode.mData, "Enqueueing 'successfully' overwriting a non TAG_INVALID_DATA... this SHOULD NOT HAPPEN\n" );				
					//------------------------

					return true;
				} 
			}

			return false;

			//Node* pNode;
 
			//UINT32 iWrite = miWriteIndex;
			//Parallel::MemoryBarrier();

			//while( true )
			//{
			//	pNode = & maSlots[ iWrite % miCapacity ];

			//	Parallel::MemoryBarrier();
			//	UINT32 iKey = pNode->mKey;
			//	Parallel::MemoryBarrier();

			//	INT32 iDiff = (INT32)iKey - (INT32) iWrite;
			//	
			//	if ( 0 == iDiff )
			//	{
			//		
			//		INT32 iVal = AtomicCompareAndSwap( (volatile INT32*) & miWriteIndex, iWrite + 1, iWrite );

			//		if(	iWrite == iVal )
			//		{
			//			break;
			//		}
			//		else
			//		{
			//			Parallel::MemoryBarrier();
			//			iWrite = iVal;
			//			Parallel::MemoryBarrier();
			//		} 
			//	}
			//	else 
			//	if( iDiff < 0)
			//	{
			//		return false;
			//	}
			//	else
			//	{
			//		Parallel::MemoryBarrier();
			//		iWrite = miWriteIndex;
			//		Parallel::MemoryBarrier();
			//	}
			//}

			//pNode->mData = _rData;

			//Parallel::MemoryBarrier();
			//pNode->mKey = iWrite + 1;
			//Parallel::MemoryBarrier();

			//return true;  
		}
		
		//--------------------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------------------		
		FORCEINLINE T	Dequeue( void )
		{  
			Node emptyNode;
			emptyNode.mData = TAG_INVALID_DATA;

			Node currentNode;
 			  
			while( miReadIndex != miWriteIndex )
			{ 
				const UINT32 iRead = miReadIndex; 
				//Parallel::MemoryBarrier();		// useless on MSVC 2005 and above, since volatile are treated as 'auto mem barriered'

				const UINT32 iSlot = iRead % miCapacity;

				currentNode.mData	= maSlots[ iSlot ].mData;
				currentNode.mKey	= iRead;

				if( TAG_INVALID_DATA != currentNode.mData )
				{
					emptyNode.mKey	= iRead + miCapacity;

					if( currentNode.mValue == AtomicCompareAndSwap64bits( & maSlots[ iSlot ].mValue, emptyNode.mValue, currentNode.mValue ) )
					{ 							
						AtomicIncrement( (volatile INT32*) & miReadIndex );

						//Parallel::MemoryBarrier();

						//------------------------
						// postcondition
						MB_ASSERT( TAG_INVALID_DATA != currentNode.mData, "Dequeuing 'successfully' a TAG_INVALID_DATA... this SHOULD NOT HAPPEN\n" );
						//------------------------

						return currentNode.mData;
					} 
				} 
			}

			return TAG_INVALID_DATA;

			
			//Node* pNode;
			//UINT32 iRead = miReadIndex;
			//Parallel::MemoryBarrier();

			//while( true )
			//{
			//	pNode = & maSlots[ iRead % miCapacity ];

			//	Parallel::MemoryBarrier();
			//	UINT32 iKey = pNode->mKey;
			//	Parallel::MemoryBarrier();

			//	INT32 iDiff = (INT32)iKey - (INT32) ( iRead + 1 );
			//	
			//	if ( 0 == iDiff )
			//	{
			//		INT32 iVal = AtomicCompareAndSwap( (volatile INT32*) & miReadIndex, iRead + 1, iRead );

			//		if(	iRead == iVal )
			//		{
			//			break;
			//		}
			//		else
			//		{
			//			Parallel::MemoryBarrier();
			//			iRead = iVal;
			//			Parallel::MemoryBarrier();
			//		}
			//	}
			//	else 
			//	if( iDiff < 0)
			//	{
			//		return TAG_INVALID_DATA;
			//	}
			//	else
			//	{
			//		Parallel::MemoryBarrier();
			//		iRead = miReadIndex;
			//		Parallel::MemoryBarrier();
			//	}
			//}
			//
			//T data = pNode->mData;

			//Parallel::MemoryBarrier();
			//pNode->mKey = ( iRead + miCapacity + 1 );
			//Parallel::MemoryBarrier();

			//return data; 
		} 

		//--------------------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------------------		
		UINT32  GetSize( void ) const
        { 
            return ((miWriteIndex) - (miReadIndex) );
        }

		//--------------------------------------------------------------------------------------------------------------------
		//--------------------------------------------------------------------------------------------------------------------		
        UINT32  GetCapacity( void ) const
        {
            return miCapacity;
        }

 
    private:

		struct Node
		{			
			union	// Use an union to avoid a compiler casting issue	
			{
				struct
				{
					UINT32	mKey;
					T		mData;		// 32 bits only !
				};
				volatile INT64	mValue;
			};
		};

		typedef UBYTE	CacheLinePadding[ CACHE_LINE_SIZE ];
 
		
		CacheLinePadding		pad2;			///<isolate each of these on its own cache line, via padding
		volatile UINT32			miReadIndex;
		
		CacheLinePadding		pad3;			///<isolate each of these on its own cache line, via padding 
        volatile UINT32			miWriteIndex; 
		
		CacheLinePadding		pad4;			///<isolate each of these on its own cache line, via padding
		UINT32					miCapacity; 
		Node*					maSlots;
    };
}

}// namespace Melting